#include <bits/stdc++.h>
using namespace std;

int p, t, n, m;
int f[2501][51][51];

long long dfs(int tot, int nums, int maxn) {
	if (f[tot][nums][maxn] != -1) return f[tot][nums][maxn];
	long long res = 0;
	if (nums == 0) {
		if (tot == 0)
			return f[tot][nums][maxn] = 1;
		else return f[tot][nums][maxn] = 0;
	}
	for (int i = 0; i <= min(tot, maxn); ++i) {
		res += dfs(tot - i, nums - 1, maxn);
		res %= p;
	}
	return f[tot][nums][maxn] = res;
}

long long qpow(long long a, long long b, long long p) {
	long long res = 1;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

long long inv(long long a, long long p) {
	return qpow(a, p - 2, p);
}

int main() {
	freopen("pr.in", "r", stdin);
	freopen("pr.out", "w", stdout);
	memset(f, 255, sizeof(f));
	scanf("%d%d", &p, &t);
	while (t--) {
		scanf("%d%d", &n, &m);
		long long res = 0, sum = dfs(0, n, m);
		for (int i = 1; i <= n * m; ++i) {
			res += dfs(i, n, m) * sum % p;
			sum += dfs(i, n, m);
			res %= p;
			sum %= p;
		}
		long long minv = inv(m + 1, p);
		for (int i = 1; i <= 2 * n; ++i) {
			res = res * minv % p;
		}
		printf("%lld\n", res);
	}
	return 0;
}

